//两数之和
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        for(int i = 0 ; i < nums.size() ; ++i)
        {
            auto it = hash.find(target - nums[i]);
            if(it != hash.end()) 
            {
                return {i,it->second};
            }
            hash.insert({nums[i],i});
        }
        return {};
    }
};

//判定是否互为字符重排
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        vector<int> hash(26);
        if(s1.size() != s2.size()) return false;
        for(size_t i = 0 ; i < s1.size() ; ++i)
        {
            hash[s1[i]-'a']++;
            hash[s2[i]-'a']--;
        }
        for(size_t i = 0 ; i < hash.size() ; ++i)
        {
            if(hash[i] != 0) return false;
        }
        return true;
    }
};

//存在重复元素
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(size_t i = 0 ; i < nums.size() ; ++i)
        {  
            if(++hash[nums[i]] > 1) return true;
        }
        return false;
    }
};

//存在重复元素Ⅱ
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        for(int i = 0 ; i < nums.size() ; ++i)
        {
            auto it = hash.find(nums[i]);
            if(it != hash.end() && abs(it->second - i) <= k)
            {
                return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};

//字母异位词分组
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;
        for(auto str : strs)
        {
            //排序
            string key = str;
            sort(key.begin() , key.end());
            auto it = hash.find(key);
            if(it != hash.end())
            {
                it->second.push_back(str);
            }
            else 
            {
                hash[key].push_back(str);
            }
        }
        vector<vector<string>> ret;
        for(auto it : hash)
        {
            if((it.second.size() != 0))
                ret.push_back(it.second);
        }
        return ret;
    }
};